#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
typedef pair<int, int> pii;
#define mp make_pair

const int MAXN = 1000, MAXM = 1000000, INF = 10001000;
int n = 9, m = 28; // |V|=n, |E|=m
int u[MAXM] = {0,0,1 ,1,2,2,8,8,3,3,4,5 ,5,6 ,1,2,2 ,3,8,4,3,4,5,6,6,6 ,7,7 };
int v[MAXM] = {1,2,2 ,3,8,4,3,4,5,6,6,6 ,7,7 ,0,0,1 ,1,2,2,8,8,3,3,4,5 ,5,6 };
int w[MAXM] = {4,8,11,8,7,1,2,6,7,4,2,14,9,10,4,8,11,8,7,1,2,6,7,4,2,14,9,10};
int first[MAXN];
int next[MAXN];
int d[MAXN], pi[MAXN];
bool done[MAXN];

void construct_adj() {
    for (int i = 0; i < n; ++i) first[i] = -1;
    for (int e = 0; e < m; ++e) {
        next[e] = first[u[e]];
        first[u[e]] = e;
    }
}

void Prim() {
    for (int i = 0; i < n; ++i) d[i] = (i == 0 ? 0 : INF);
    priority_queue<pii, vector<pii>, greater<pii> > q;
    q.push(mp(d[0], 0));
    while (!q.empty()) {
        pii u = q.top(); q.pop();
        int x = u.second;
        if (done[x]) continue;
        done[x] = true;
        for (int e = first[x]; e != -1; e = next[e]) if (!done[v[e]]) {
            if (d[v[e]] > w[e]) {
                d[v[e]] = w[e];
                q.push(mp(d[v[e]], v[e]));
                pi[v[e]] = x;
            }
        }
    }
}

int main() {
    construct_adj();
    Prim();
    for (int i = 0; i < n; ++i) cout << pi[i] << ' ';
    cout << endl;
}

